20. 有效的括号

Solution Tips

方案一: 栈

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

var isValid = function (s) {
  function Stack() {
    var items = []
    this.push = function (item){
      console.log(item)
      items.push(item)
    }
    this.pop = function (){
      return items.pop()
    }
    this.isEmpty = function(){
      return items.length === 0 
    }
  }

  let stack = new Stack()
  // 观察结构可以发现，即是括号的类型不同，只有匹配的情况下才可以成功pop
  let map = {
    '[':']',
    '(':')',
    '{':'}',
  }
  for (let i = 0; i < s.length; i++) {
    // 左边的执行push操作，判断是否相等
    if(/\(|\[|\{/.test(s[i])){
      stack.push(s[i])
    }else{
    // 右边的执行pop操作
      let pop = stack.pop()
      console.log(map[pop],s[i])
      if(map[pop] !== s[i]){
        return false
      }
    }
  }

  // 循环执行完毕，栈为空，return true
	return stack.isEmpty()
}

20. 有效的括号

Similar Question

Solution Tips

方案一: 栈